def optimal_bst(keys, frequencies):  
    n = len(keys)  
      
    # e[i][j] 表示从键 i 到键 j 的最优BST的预期搜索成本  
    e = [[0] * n for _ in range(n)]  
      
    # root[i][j] 表示从键 i 到键 j 的最优BST的根节点  
    root = [[-1] * n for _ in range(n)]  
      
    # w[i][j] 表示从键 i 到键 j 的所有键的频率之和  
    w = [[0] * n for _ in range(n)]  
      
    # 初始化权重数组  
    for length in range(1, n + 1):  
        for i in range(n - length + 1):  
            j = i + length - 1  
            w[i][j] = sum(frequencies[i:j+1])  
      
    # 填充DP表  
    for length in range(1, n + 1):  
        for i in range(n - length + 1):  
            j = i + length - 1  
            e[i][j] = float('inf')  
            if length == 1:  
                e[i][j] = frequencies[i]  
                root[i][j] = i  
            else:  
                for r in range(i, j + 1):  
                    left_cost = e[i][r-1] if r > i else 0  
                    right_cost = e[r+1][j] if r < j else 0  
                    t = left_cost + right_cost + w[i][j]  
                    if t < e[i][j]:  
                        e[i][j] = t  
                        root[i][j] = r  
      
    return e, root, w  
  
# 示例  
keys = [1, 2, 3, 4, 5]  
frequencies = [5, 9, 12, 13, 5]  
  
# 调用函数  
e, root, w = optimal_bst(keys, frequencies)  
  
# 输出预期搜索成本  
print("Expected search cost of the optimal BST:", e[0][len(keys)-1])  
  
# 打印根节点信息  
for i in range(len(keys)):  
    for j in range(i, len(keys)):  
        print(f"Subtree {keys[i]}-{keys[j]} has root {root[i][j]}")
        #root[i][j] 存储的是最优BST的根节点的键索引（在 keys 列表中的索引），而不是键的实际值